Luồng trên mạng

Trong lý thuyết đồ thị, một luồng trên mạng, thường được gọi tắt là luồng, là một cách gán các luồng (dòng chảy) cho các cung của một đồ thị có hướng (trong trường hợp này được gọi là một mạng vận tải) trong đó mỗi cung có một khả năng thông qua, sao cho dung lượng luồng qua một cung không vượt quá khả năng thông qua của nó. Ngoài ra, ta còn có một điều kiện rằng dung lượng luồng vào một nút phải bằng dung lượng luồng ra khỏi nút đó, ngoại trừ trường hợp nó là một nút phát (hay nút nguồn) - nơi chỉ có dòng ra, hoặc một nút thu - nơi chỉ có luồng vào. Một mạng vận tải có thể được dùng để giả lập giao thông trên một hệ thống đường sá, dòng chảy trong các đường ống, dòng trong một mạch điện, hoặc bất cứ cái gì tương tự di chuyển qua một mạng lưới gồm các nút.